class TreeNode:
    def __init__(self,val):
        self.val = val
        self.right = None
        self.left = None

def constructTree(nums):
    if not nums:
        return None
    maxVal = float("-inf")
    index = 0
    for i in range(len(nums)):
        if nums[i] > maxVal:
            maxVal = nums[i]
            index = i

    root = TreeNode(maxVal)
    root.left = constructTree(nums[:index])
    root.right = constructTree(nums[index+1:])
    return root

class Solution:
    def kthSmallest(self,root,k):
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k==0:
                return root.val
            root = root.right


class Solution2:
    def __init__(self, root):
        self.root = root
        self._node_num = {}
        self._count_node_num(root)

    def kth_smallest(self, k):
        node = self.root
        while node:
            left = self._get_node_num(node.left)
            if left < k - 1:
                node = node.right
                k -= left + 1
            elif left == k - 1:
                return node.val
            else:
                node = node.left

    def _count_node_num(self, node):
        if not node:
            return 0
        self._node_num[node] = 1 + self._count_node_num(node.left) + self._count_node_num(node.right)
        return self._node_num[node]

    def _get_node_num(self, node):
        return self._node_num[node] if node is not None else 0

# 平衡二叉树判断
def isValidBST(root, min, max):
    if root == None:
        return True
    if min != None and root.val <= min.val:
        return False

    if max != None and root.val >= max.val:
        return False

    return isValidBST(root.left, min, root) and isValidBST(root.right, root, max)



if __name__=="__main__":
    nums = [3,2,1,6,0,5]
    root = constructTree(nums)
    s = Solution()
    r = s.kthSmallest(root,2)
    isValidBST(root, None, None)
    print(r)